|
In formal language theory, an LL grammar is a formal grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser that constructs a rightmost derivation). A language that has an LL grammar is known as an LL language. These form subsets of deterministic context-free grammars (DCFGs) and deterministic context-free languages (DCFLs), respectively. One says that a given grammar or language "is an LL grammar/language" or simply "is LL" to indicate that it is in this class. LL parsers are table-based parsers, similar to LR parsers. LL grammars can alternatively be characterized as precisely those that can be parsed by a predictive parser – a recursive descent parser without backtracking – and these can be readily written by hand. This article is about the formal properties of LL grammars; for parsing, see LL parser or recursive descent parser. ==Relation to LL parsers== There is a separate LL(''k'') parser for each natural number ''k'' (0, 1, 2, ...). A LL parser is called a LL(''k'') parser if it uses ''k'' tokens of lookahead when parsing a sentence. A LL(''k'') parser recognizes the languages generated by some ''ε''-free LL(''k'') grammar. As allowing more tokens of lookahead makes the parser strictly more powerful, the languages that can be recognized with a LL(''k'') parser are a strict subset of the languages that can be recognized by a LL(''k+n''), ''n > 0'' parser. This creates a strictly increasing sequence of sets: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊ …. Since these are all DCFLs, a corollary is that for any fixed ''k'', there are DCFLs that cannot be recognized by a LL(''k'') parser. An LL parser is called an LL( *) parser if it is not restricted to a finite ''k'' tokens of lookahead, but can make parsing decisions by recognizing whether the following tokens belong to a regular language (for example by use of a Deterministic Finite Automaton), and accordingly there are the set of LL( *) grammars and the set of LL( *) languages. Although ''ε''-free LL(''k'') grammars are considered for LL(''k'') parsers, allowing ''ε''-rules increases the expressive power of the grammar: For every ''ε''-free LL(''k+1'') grammar, there exists a LL(''k'') grammar with ''ε''-rules that generates the same language. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「LL grammar」の詳細全文を読む スポンサード リンク
|